Content addressable memories (CAMs) are high-speed associative memory structures which may be used to determine address mappings or translations, for example. A CAM is accessed using the content that may be stored therein. For example, a data word of interest can be stored anywhere in a CAM, and all entries of the CAM are searched to see if the data word is present. If present, an index or address where the data word is found is returned by the CAM.
In order to implement the above functionality of searching through all entries for each access, a CAM may be implemented as an array comprising CAM cells arranged in rows and columns, with each CAM cell including a storage cell (e.g., a static random access memory (SRAM) cell) and comparison circuitry. Each row of CAM cells may store a data word. The comparison circuitry for a storage cell in a row may be coupled to a matchline that indicates whether a data word being searched matches the stored data word in the row.
For improved performance, it is desirable to allow a CAM array to be searched for a first data word, for example, in parallel with writing a second data word to be stored in the CAM. However, since searching for the first data word in the CAM involves searching all rows for the first data word, it is possible that there is a simultaneous search operation for the first data word and a write operation for the second data word on the same row. This simultaneous search and write on a row is referred to as a search and write conflict on the row. A search and write conflict can cause a potential match or hit (e.g., for the first data word that is searched) to turn into a miss because the stored data word is overwritten by the write of the second data word. It is also possible that the first data word may not be present in the CAM, but a write of the second data word to a searched row may turn the miss for the first data word into a hit or a match due to the second data word being written to the searched row. If a miss for a row is turned into a match or a hit, the matchline for the row may be caused to float, thus entering an unknown or unpredictable state.
Conventional efforts to mitigate search and write conflicts involve preventing search operations from taking place in the same clock cycle as write operations, which leads to poor performance, as noted above. Accordingly, there is a need for eliminating or mitigating the negative effects of search and write conflicts in CAMs, without degrading performance.